#include <iostream>
#include <queue>
#include <memory>

using std::cout;
using std::endl;
using std::queue;
using std::shared_ptr;
using std::make_shared;

struct Node;

using NodeP = shared_ptr<Node>;

struct Node{
    Node(int w, int v, int l, NodeP p, bool i)
    :weight(w), value(v), level(l), parent(p), isleft(i){}    

    int weight;
    int value;
    int level;
    NodeP parent;    
    bool isleft;
};

NodeP bestNode;
queue<NodeP> que;

void addLiveNode(int weight, int value, int level, NodeP parent, bool isleft, int bestv, int bestw)
{
    que.push(make_shared<Node>(weight, value, level, parent, isleft)); 

    if(level == 3 && bestv == value){
        bestNode = que.back(); 
    }
}

int maxBound(int *v, int level)
{
    int ret = 0;
    for(int i{level + 1}; i < 3; i++){
        ret += v[i];
    }
    return ret;
}

auto func(int *w, int *v, int c)
{
    NodeP node;
    int i = 0;
    int cw = 0, cv = 0;
    int bestv = 0, bestw = 0;
    while(i < 3){
        if(cw + w[i] <= c){
            if(cv + v[i] > bestv){
                bestv = cv + v[i];
            }

            addLiveNode(cw + w[i], cv + v[i], i + 1, node, true, bestv, bestw);
        }

        // 这里不设为 >= 会导致最后一个元素不能不被选择，一直处于死循环中
        if(cv + maxBound(v, i) >= bestv){
            addLiveNode(cw, cv, i + 1, node, true, bestv, bestw);
        }

        node = que.front();
        que.pop();
        i = node->level; 
        cw = node->weight;
        cv = node->value;
    }

    return std::tuple<int, int>(bestNode->weight, bestv);
}

int main(int args, char *argv[])
{
    int w[] = {12, 8, 15}; 
    int v[] = {6, 9, 8}; 
    auto [bestw, bestv] = func(w, v, 90);
    cout << bestw << ", " << bestv << endl;
    return 0;
}